package me.mysearch;

public class RightMostDemo1 {
    public static void main(String[] args) {
        int[] arr = {1, 5, 6, 4, 4, 4, 7, 8, 9};
        int result = binarySearchRightmost1(arr, 4);
        System.out.println(result);
    }

    public static int binarySearchRightmost1(int[] a, int target) {
        //找重复的元素，必须是最右边的
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                //目标值和中间值相等
                //先记录候选位置
                candidate = m;
                //再往右找
                i = m + 1;
            }
        }
        return candidate;
        /*更有用的返回值
        返回<=目标值最靠右的索引
        return i - 1;*/

    }
}
